The present invention is directed to a method of providing authentication assurance in a keybinding system. More particularly, the present invention is directed to a method in which edges along a path between a source key and a target key have a level of assurance attributed thereto which can be used to assist a user in selecting among a plurality of available paths.
With the growth of electronic transactions over open networks, it has been desirable to explore the possibility of conducting electronic commerce over those networks. Such commerce typically requires certain levels of confidentiality to assure users that critical information which may be necessary to conduct a transaction is only used by the parties to the transaction in question and not other parties who might otherwise make improper use of the information. Mindful of this desire to maintain confidences many systems have employed encryption techniques for rendering the confidential information largely indecipherable in the absence of a key associated with the encryption technique.
Once it is determined to utilize encryption with respect to transactions, the next issue arises concerning how to either permit or limit access to the key information. Determining the owner of a public key, or conversely determining the public key for a user, appears to be a basic ingredient for executing transactions securely in any large scale open system. Due to the lack of a single authority for providing this information in a system having many different administrative domains, many systems resort to authentication by a path or chain of authorities. In accordance with such a model a user locates a path or sequence of authorities such that: 1) the user can authenticate the first authority in the path; 2) each authority in the path can authenticate the next authority in the path; and 3) the last authority in the path is in fact the targeted person or key of interest. If the user trusts every authority on the path, then perhaps it can believe that a proper name-to-key binding has been obtained.
A path of authorities may be weak because it relics on the correctness of every authority in the path. If any authority in the path incorrectly authenticates the next authority, then the user can be misled regarding the authentication of subsequent authorities in the path, including the target. A natural approach to increasing assurance in the authentication of the target would be to use multiple paths. Multiple paths have been shown to be useful in systems where the lack of an enforced certification structure naturally leads to the existence of multiple paths. Multiple paths may also arise in hierarchical certification structures as soon as cross certification is allowed.
An example of multiple paths from a trusted source key to a target key is shown in FIG. 1. In a hierarchical certification structure, child-to-parent and cross certification can be performed. Each of the nodes, 101 to 109, denotes a public key. A line between public keys denotes a certificate that contains the key to which that edge points and which can be verified with the key from which that edge originates. While the notion of obtaining redundant confirmation of the target name-to-key binding via multiple paths may be appealing the assurance provided by these paths may be unclear, especially if they have authorities in common or authorities that act in a correlated way. When combined with ambiguities in the assertions that authorities make and the ambiguities regarding who is actually making the assertions it may be difficult to complete the authentication with any confidence.
Several researchers have thus proposed metrics for measuring an assurance provided by a set of paths. For example. a metric might take as input other such paths of authorities and return a numeric value, where a higher value indicates greater confidence in the name-to-public-key binding (for the target name or public key) that those paths support. Various metrics use certificates for authentication.
One such certificate scheme is Recommendation X.509, International Telegraph and Telephone Consultative Committee (CCITT). X.509 deals with Authentication Frameworks for Directories. Within X.509 is a specification for a certificate which binds an entity""s distinguished name to its public key through the use of a digital signature. For a further understanding of the environment in which the present invention may be implemented additional description of alternative metrics and their shortcomings will now be provided. Each metric below is described only to the extent necessary to set the stage for the rest of the description of the invention and some will be described in less detail than others. Furthermore, each of the metrics described below operates in the context of a model that consists of a directed graph whose nodes and edges are labeled in various ways. No two metrics share the same model. that is the same graph. Except where explicitly stated otherwise, the review of the performance of each metric is based on a model containing only consistent information, that is, where there are no conflicting reports regarding the owner (or other attributes) of a key. While how a metric behaves on conflicting information is important, this information is omitted to simplify the discussion. For purposes of the discussion an entity is something that possesses and makes use of a private/public key pair, for example a person, an authentication server, or certification authority. The user is the person applying the metric for the purpose of gaining assurance in a name-to-key binding.
The three main areas in evaluating a metric are the meaning of the values output by the metrics, the sensitivity of the metric (the extent of which the metric outputs can be manipulated by malicious behavior. e.g., compromise of cryptographic keys) and the effectiveness of using the metrics in a practice environment.
The most basic desideratum of a metric is that its output be meaningful. The metrics discussed below strive for this, although some achieve it better than others.
The metrics used for comparison in the present application are the Beth. Borcherding, and Klein metric, the Zimmermann metric, the Maurer metric, and the Reiter-Stubblebine metric. Each of these metrics, as described below, operates using a directed graph. The graph consists of nodes and edges as shown in FIG. 1.
Beth-Borcherding-Klein
The Beth-Borcherding-Klein metric takes as an input a set of trust relationships that can be represented by a directed graph. The nodes of the graph are entities. There are two types of edges in this graph. The first type is a xe2x80x9cdirect edgexe2x80x9d. The direct edge Axe2x86x92B means that A believes it can authenticate (i.e., has the public key for) B. The second type of edge is a xe2x80x9crecommendation edgexe2x80x9d; the recommendation Axe2x86x92B represents that A trusts B to authenticate other entities or to recommend other entities to authenticate or further recommend. Associated with each recommendation and direct edge is a value in the range [0, 1]. In the case of a direct edge Axe2x86x92B, this value is A""s estimation of the probability that A really holds the correct public key for B. The value on a recommendation edge Axe2x86x92B represents the degree of A""s trust in B as a recommender, where higher values indicate stronger trust.
Given a specific query, say user A wanting the public key for entity B, the metric computes a value in the range [0, 1], using all paths from A to B whose last edge is direct and whose other edges are recommendation edges, such as Axe2x86x92Cxe2x86x92Dxe2x86x92B.
The Beth-Borcherding-Klein metric, however, suffers from a number of deficiencies. First, evaluating this metric requires the user to collect values from other entities for the various direct and recommendation edges. Before the user can safely assign a value to the edge Axe2x86x92B or Axe2x86x92B, the user must authenticate this value as having come from A. Assuming that this authentication is performed cryptographically (e.g., via a certificate), again the user is asked to determine a key that can be used to authenticate A in order to form the model for the query she wants answered. Thus, the user is forced to infer a binding between a key and its owner. This can be disadvantageous.
Additionally, the Beth-Borcherding-Klein metric is overly sensitive to misbehavior by one of the entities. In fact, this metric has the property that a single misbehaving entity can increase or decrease the result of the metric arbitrarily.
To show this, recall that the specific rules used to compute the Beth-Borcherding-Klein metric include that each edge in the Beth-Borcherding-Klein model is labeled with a value in the range [0,1]. Suppose that A wants to authenticate (determine the public key for) B. Beth, et al., propose and justify the following rules for computing an aggregate xe2x80x9cscorexe2x80x9d for A""s authentication of B based upon the values on the edges of the paths connecting A to B.
1. If there is a path Axe2x86x92. . .xe2x86x92C with recommendation value v1, and a recommendation edge Cxe2x86x92D with value v2, then the path Axe2x86x92 . . . xe2x86x92Cxe2x86x92D has recommendation value v1. v2.
2. If there is a path Axe2x86x92. . .xe2x86x92C with recommendation value v1 and a direct edge Cxe2x86x92B with value v2, then the path Axe2x86x92. . .xe2x86x92Cxe2x86x92B has direct trust value 1xe2x88x92(1xe2x88x92v2)v1.
3. If for each 1xe2x89xa6ixe2x89xa6m, there are ni distinct paths from A to B ending with the edge Cixe2x86x92B, with direct trust values vi,1 . . . ,vi,ni, then the combined direct trust value is             V      com        ⁡          (              A        ,        B            )        =      1    -                  ∏                  i          =          1                m            ⁢                                    ∏                          n              i                        j                    ⁢                      =                          1              ⁢                              (                                  1                  -                                      v                                          i                      ,                      j                                                                      )                                                              n          i                    
To see an example of applying these rules, consider the graph of FIG. 2. By rules 1 and 2 above, paths Axe2x86x92Cxe2x86x92Fxe2x86x92B, Axe2x86x92Dxe2x86x92Gxe2x86x92B, and Axe2x86x92Exe2x86x92Gxe2x86x92B yield direct trust values of 0.204, 0.173, and 0.765, respectively. Combining these with rule 3, we get vcom(A,B)=0.649.
Now consider the graph of FIG. 3, which is a manipulation of the graph in FIG. 2 caused by D""s misbehavior. Here, D has created additional artificial paths from A to B through other nodes H, I, J that D xe2x80x9cinventedxe2x80x9d for the purposes of altering the metric output. The trust value assigned to path Axe2x86x92Dxe2x86x92Hxe2x86x92B by rules 1 and 2 above is 0.821, and similarly for Axe2x86x92Dxe2x86x92Ixe2x86x92B and Axe2x86x92Dxe2x86x92Jxe2x86x92B. Rule 3 then yields a combined trust value of vcom(A,B)=0.998. What this example shows is that a single misbehaving node, by manipulating the graph used in the computation of the Beth-Borcherding-Klein metric, can drive the metric arbitrarily close to any value it chooses, and in particular to a high value that inflates the confidence expressed by the metric. Thus, in the face of malicious entities, it is unclear that Beth-Borcherding-Klein is a useful metric.
We should note that Beth-Borcherding-Klein allows for the exclusion of paths based on xe2x80x9cconstraint setsxe2x80x9d, and thus a user that is familiar with the graph structure could, e.g., explicitly exclude paths through H, I, and J. If the user is not familiar with what the graph structure should be, however, then the user might have no basis to exclude such paths.
Finally, the Beth-Borcherding-Klein metric is unable to be computed efficiently and additional edges added to its model can increase or decrease the metric output by an arbitrary amount. Therefore. the metric""s output on partial information may give the user little insight into the xe2x80x9cactualxe2x80x9d quality of the name-to-key binding.
Maurer
The Maurer metric takes a directed graph as an input, as well. As in Beth-Borcherding-Klein, the nodes of this graph are entities and there are two types of edges, xe2x80x9cdirectxe2x80x9d and xe2x80x9crecommendationxe2x80x9d. However, the semantics of these edges are subtlety different in the Maurer model, in that these edges represent syntactic constructs, e.g., certificates. A direct edge Axe2x86x92B means that the user evaluating the metric xe2x80x9cholds a certificate for B""s public key (allegedly) issued and signed by entity Axe2x80x9d. Similarly, a recommendation edge Axe2x86x92B denotes that the user is in possession of a recommendation (for recommending or authenticating other entities) for B allegedly signed by entity A. Associated with each recommendation and direct edge is a value in the range [0, 1], called a confidence parameter, that is assigned by the entity that created (the construct represented by) the edge. Given a specific query, e.g., user A wanting the public key for B. the metric computes a confidence value in the range [0, 1] for the key that the model suggests is B""s using the confidence parameters specified for the edges as probabilities.
The Maurer metric also has several shortcomings. Like the Beth et al. metric, Maurer forces a user to infer a binding between a key and its owner. In Maurer, the edge Axe2x86x92B exists in the model if the user evaluating the metric xe2x80x9cholds a certificate for B""s public key (allegedly) issued and signed by entity Axe2x80x9d. Maurer uses the word xe2x80x9callegedlyxe2x80x9d because xe2x80x9cwithout verification, there exists no evidence that the certificate was indeed issued by the claimed entity.xe2x80x9d Put another way, when the entity that allegedly signed the certificate is claimed with the certificate, this claim is at best a hint and at worst an opportunity to be misled. It is presumably for this reason, however, that in some systems a certificate includes no claim at all of the entity that signed it, but rather only a claim of the key that signed it. For example, in some other metrics the certificate indicates only an identifier for the public key that can be used to verify the signature on the certificate. In such cases. how a certificate should be represented in the Maurer model is ambiguous, and presumably the user must infer the certificate""s signer from other certificates for the key that verifies the certificate""s signature. One interpretation even allows a certificate to be represented by multiple edges if different certificates indicate different owners for its verification key.
Additionally, in Maurer the meaning of the model""s parameters can be ambiguous. Specifically, the policy that dictates how confidence parameters are assigned to certificates and recommendations is left unspecified. This raises two concerns. First, Maurer""s interpretation of these confidence parameters as probabilities is not sufficiently justified. Indeed, the suggested means for determining confidence parameters (e.g., xe2x80x9cspeaker identification over a telephone line should be assigned a confidence parameter of at most 0.95xe2x80x9d) seem to bear no relationship to random experiments. Second. since the user evaluating the metric presumably must adopt the confidence parameters for certificates and recommendations determined by their creators, any ambiguities in the semantics of these parameters can be compounded by misinterpretation by the user.
Maurer also falls to provide an output that is intuitive, that is, it is difficult to write down a straight-forward natural language sentence to describe the meaning of the output. This metric computes a confidence value for a name-to-key binding as the probability that the binding can be derived from the initial view of the user where the random event is the selection of the initial view, i.e. the selection of a random subset of the certificates and recommendations available to the user, using a distributed defined by the confidence parameters assigned to edges. As this experiment does not correspond to a familiar procedure in the real world, it remains to be seen whether the average user is willing to understand and believe a metric computed in this way.
Maurer also is susceptible to manipulation via misbehavior. Maurer fails to be explicit about how sensitive a score is that it returns. The score returned by the Maurer metric can range from being very sensitive (e.g., if it is computed using only a single path from the source to the target) to very tolerant (e.g., if many disjoint paths are involved).
Finally, the Maurer metric cannot be computed efficiently.
Reiter-Stubblebine.
Reiter and Stubblebine developed two related metrics. The Reiter-Stubblebine metrics take a directed graph as an input, but this graph differs from those for the Beth-Borcherding-Klein and Maurer metrics. In this case, the nodes of the graph are public keys (actual keys, with no references to any entities), and an edge K1xe2x86x92K2 means that the user evaluating the metric has a certificate signed by the private key corresponding to K1 (i.e., K1 can be used to verify the signature) and that assigns attributes to K2. The attributes bound to K2""s owner (among other things, perhaps), are included as a label on the edge K1xe2x86x92K2. There are no other values associated with edges or nodes.
Each metric takes as an input the above graph, a key that the user wishes to authenticate (the target key), a key that the user trusts (the source key, e.g., her own), and a bound xe2x80x9cbxe2x80x9d on the length of paths to consider. The first metric returns a maximum set of node-disjoint paths of length at most xe2x80x9cbxe2x80x9d from the source key to the target key. The second metric returns an integer xe2x80x9ckxe2x80x9d and a set of paths of length at most b from the source to the target such that k nodes have to be removed (compromised) to break all the paths; the value of k returned is the maximum k for which such a set of paths exists, and is called the xe2x80x9cconnectivityxe2x80x9d from the source key to the target key. If we insist that these metrics produce a numeric output, then in the case of disjoint paths it would be the number of disjoint paths that it returns, and in the other case it would be the connectivity.
The Reiter-Stubblebine model consists solely of a graph whose nodes represent keys and whose edges represents certificates available to the user evaluating the metric. In contrast to other metrics, the Reiter-Stubblebine metric makes no effort to take into account trust relationships or recommendations among entities; indeed, entities appear nowhere in its model (except named within the labels attached to edges, but the metric does not consider these). As such, when the metric returns a set of disjoint (or connective) paths, the user is left to determine whether the paths are xe2x80x9cgood enoughxe2x80x9d based upon who she trusts and the labels on the various edges in the paths. Even worse, since the metric does not take into account trust information, it may actually inhibit the user""s decision on whether to adopt the recommended name-to-key binding, by including in its returned paths some nodes and edges that the user is unfamiliar with, at the expense of others that the user would have preferred. In summary. this model does not take into account as much information that is relevant to the authentication decision as possible.
The Reiter-Stubblebine metric also is susceptible to making decisions that could affect authentication, while hiding the fact from the user, even though it may be reached with ambiguous rules. The Reiter-Stubblebine metric, if interpreted as returning simply a number of disjoint paths, would have the problem of determining if two keys are adequately independent for the purposes of independent certification. In reality, the implementation of the Reiter-Stubblebine metric in PathServer returns the actual paths, leaving the determination problem for the user to figure out.
The Reiter-Stubblebine metric is also disadvantageous because it cannot be computed efficiently.
Zimmermann
The metric attributed to Zimmermann uses the pretty good privacy (PGP) public key management systems. Zimmermann""s graph resembles (but also preceded) the Reiter-Stubblebine graph. Its nodes are keys. and the edge K1xe2x86x92K2, labeled with attributes, represents a certificate that binds these attributes to K2 and that can be verified with K1. It differs from the Reiter-Stubblebine graph, however. in that the user augments each node with a trust value, which is one of unknown, entrusted, marginally trusted, or fully trust.
PGP computes the legitimacy of each node as follows. PGP first declares to be legitimate the node Ko representing the user""s key and any node K such that Koxe2x86x92K is an edge in the graph. PGP then repeats the following until no more keys can be determined to be legitimate: if for some node K, either (i) there is an edge to K from a legitimate fully trusted node or (ii) there are edges to K with identical labels from two legitimate marginally trusted nodes, then K is declared legitimate. The numbers of edges required from fully trusted or marginally trusted nodes can be adjusted, but one and two are the defaults, respectively. In practice, determinations of node legitimacy are interwoven with assigning trust values to nodes. That is, a trust value is assigned to a node only after it has been determined to be legitimate and thus its owner is assumed to be known (i.e., named on the one edge to it from the fully trusted node or the two edges to it from the marginally trusted nodes). For the purposes of modeling, however, the end result is the same.
Intuitively, PGP might not be considered to implement a metric, but rather to simply determine whether a key is legitimate (authenticated) according to the policy described above. Alternatively, one might construct a metric from PGP by using multiple queries to PGP with different parameters to determine. e.g., the actual number of edges from legitimate marginally trusted nodes to a target node.
Zimmermann has several deficiencies that need to be examined. Zimmermann, like Reiter Stubblebine, is susceptible to making automated decisions on ambiguous information while keeping that decision hidden from the user. In PGP a user assigns a level of trust to each node (key), which is one of unknown, untrusted, marginally trusted, and fully trusted, based upon its apparent owner. By default, PGP will declare a key legitimate if it is certified by one fully trusted key or two marginally trusted keys. It is in this mechanism that PGP strays. It is often the case that a single user has two or more keys and uses each of these keys to certify another. An actual example is shown in Table 1 below. The first line describes a key-to-name binding, namely the binding between the key with identifier C7A966Dd and the name Philip R. Zimmermann  less than prz@acm.org greater than . The second and third lines shown that Jeffrey I. Schiller  less than jis@mit.edu greater than  has signed this binding with two different keys, namely those identified with ODBF906D and 4DOC4EE1.
Now, if the user tells PGP and Jeffrey I. Schiller  less than jis@mit.edu greater than  is marginally trusted introducer, then PGP will mark keys ODBF906D AND 4DOC4EE1 as marginally trusted, and therefore key C7A966DD will be declared legitimate (i.e., bound to Philip R. Zimmermann  less than prz@acm.org greater than ). This occurs despite the fact that only one marginally trusted person was involved in certifying the key, whereas such a conclusion should supposedly require two.
This example points to a deeper problem than just an oversight in the PGP implementation. Rather, it points to the difficulty of determining if two keys are adequately independent for the purposes of independent certification, and we are aware of no foolproof way to automate this decision. For example, simply verifying that the names bound to ODBF906D and 4DOC4EE1 are different does not suffice, since they may have different email addresses but still indicate the same person, or since the key owners may not be the same but still act in a correlated way (e.g., two close friends). It is believed that this decision should not be hidden from the user. Appealing to the user impacts the case-of-use of the metric, however, as this decision can be unclear even for the user.
The Zimmermann metric is also disadvantageous in that while the metric admits a simple operational (i.e., algorithmic) description, the intuitive property that separates legitimate from illegitimate keys is undocumented and non-obvious.
Finally, it is debatable whether the Zimmerman metric is simple or difficult to utilize in a large-scale system. Although PGP is presently used as a standalone program, one may argue that the ease-of use of the metric has been achieved at the cost of hiding certain decisions from users that should not be hidden.
In view of the foregoing, it can be appreciated that a substantial need exists for a method and apparatus that combines the attractive features of each of the metric to be used in an authentication environment.
The disadvantages of the prior art are alleviated to a great extent by a method and apparatus that combines the features of each of the authentication metric to be used in an authentication environment. According to the present invention, a method for generating a certificate for use in authenticating a target is disclosed. The method includes the steps of obtaining a first key; assigning at least one attribute to the first key; assigning a liability value to the combination of the first key and at least one attribute; and signing a combination of the first key, the at least one attribute and the liability value with a second key.
With these and other advantages and features of the invention that will become hereinafter apparent, the nature of the invention may be more clearly understood by reference to the following detailed description of the invention, the appended claims and to the several drawings attached herein.